---
title: "6、七段码"
created: 2025-11-28
tags:
  - 算法
---

# 6、七段码

## 题目 [七段码](https://www.lanqiao.cn/paper/3836/problem/595/)

![[image-dff1bfe9.png]]

## 思路分析

二极管 不外乎就是亮与不亮 可以联想到用二进制来表示

每个二进制位来表示一段二极管

a b c d e f g

1 2 3 4 5 6 7

1 1 1 1 1 1 1

要连续的发光才合法

所以问题应该就是转变成了 0000000~1111111中有多少个

满足

亮一个 1 2 3 4 5 6 7 上为1

亮两个 1,2 1,6 2,3 2,7 3,4 3,7 4,5 5,6 5,7 6,7 位上同时为1

……

```cpp
#include<bits/stdc++.h>

using namespace std;

bool check(int x){

	bitset<8> temp(x);

	string s=temp.to_string();

	if((s[0]==s[1] && s[0]=='1')

		||

	   (s[0]==s[5] && s[0]=='1')

	    ||

	   (s[1]==s[2] && s[1]=='1')

	    ||

	   (s[1]==s[6] && s[1]=='1')

	    ||

	   (s[2]==s[3] && s[2]=='1')

	    ||

	   (s[2]==s[6] && s[2]=='1')

	    ||

	   (s[3]==s[4] && s[3]=='1')

	    ||

	   (s[4]==s[5] && s[4]=='1')

	    ||

	   (s[4]==s[6] && s[4]=='1')

	    ||

	   (s[5]==s[6] && s[5]=='1')

      //…………一个的情况 两个的情况 三个的情况

        )

	   return true;

	return false;

}

int  main()

{

	long long cnt=0;

	for(int i=0;i<(1<<7);i++)

		if(check(i))

			cnt++;

	cout<<cnt;

	return 0;

}
```

这还写什么代码 还不如手算出来了

这里代码可以借鉴的东西就是 可以把一个十进制数用bitset转变成二进制数

再把二进制数 用.to\_string()方法转变成字符串处理

直接可以手写了 方案数不多

亮一个灯:1、2、3、4、5、6、7，共7种 亮两个灯:12、13、24、25、34、36、45、46、57、67，共10种 亮三个灯:123、124、125、134、136、234、245、246、257、345、346、367、456、457、467、567，共16种
亮四个灯，这时不要直接数四个灯，情况与灭三个灯是等价的，数三个灯比数四个灯简单。注意灭三个灯后其他的四个亮灯是连续的:灭123、124、125、126、127、134、135、136、137、157、167、245、257、267、346、357、367、457、467、567，共20种
亮五个灯:数灭两个灯的情况:灭12、灭13、灭14、…等，共19种 亮六个灯:数灭一个灯的情况，有7种 亮七个灯:有1种 共80种

正解应该是dfs

又是想到二进制枚举结果给我dfs 啧

将7段码数码管的每个段视为图的一个节点，节点之间的连通关系表示为图的边

问题转化为了在一个由7个节点构成的图中，找出所有点亮的节点形成单个连通分量的组合

每个段都有点亮和不点亮两种状态，指数型枚举

在每个DFS的递归调用中，利用并查集来检查当前点亮的段是否都在同一个连通分量中，路径压缩，快速判断当前点亮的所有段是否能够通过已有的边相连，形成一个连通分量

这题dfs比较容易想 主要是并查集有点生疏

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N = 10;

int g[N][N]; // 邻接矩阵，表示数码管各段之间的连通关系

int p[N]; // 并查集的父节点数组

bool st[N];

int res;

// 添加边，即设置数码管的两个段是相连的

void add(int a, int b) {

    g[a][b] = g[b][a] = 1;

}

// 并查集查找函数,路径压缩

int find(int x) {

    if(p[x] != x)

        return p[x] = find(p[x]);

    return p[x];

}

// 检查当前点亮的数码管段是否形成单个连通分量

bool check() {

    for(int i = 1; i <= 7; i++)

        p[i] = i; // 初始化并查集

    for(int i = 1; i <= 7; i++) {

        for(int j = 1; j <= 7; j++) {

            if(st[i] && st[j] && g[i][j])

                p[find(j)] = find(i); // 合并连通的段

        }

    }

    int cnt = 0;

    for(int i = 1; i <= 7; i++)

        if(st[i] && p[i] == i)

            cnt++; // 计算连通分量数量

    return cnt == 1; // 只有当存在一个连通分量时，返回true

}

void dfs(int u) {

    if(u > 7) {

        if(check())

            res++;

        return;

    }

    st[u] = true;

    dfs(u + 1);

    st[u] = false;

    dfs(u + 1);

}

int main() {

    // 设置数码管段之间的连通关系

    add(1,2); add(1,6);

    add(2,3); add(2,7);

    add(3,4); add(3,7);

    add(4,5); add(5,6); add(5,7);

    add(6,7); add(6,1);

    dfs(1);

    cout<<res<<endl;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[5、跑步锻炼|5、跑步锻炼]] 🏠 [[00-刷题理模型]] ➡️ [[7、成绩统计|7、成绩统计]]